SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Decoding methods</title>

</head>

Decoding methods

</h1>

</header>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, decoding is the process of translating received messages into <a href="Code_word_(communication)" title="Code word (communication)">codewords</a> of a given <a href="Code" title="Code">code</a>. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a <a href="Noisy_channel" class="mw-redirect" title="Noisy channel">noisy channel</a>, such as a <a href="Binary_symmetric_channel" title="Binary symmetric channel">binary symmetric channel</a>.

<div class="mw-heading mw-heading2"><h2 id="Notation">Notation</h2></div>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subset \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./f2747dab950a24e090084ba23a584c5db2fe077f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.504ex; height:2.843ex;" alt="{\displaystyle C\subset \mathbb {F} _{2}^{n}}" loading="lazy"> is considered a <a href="Binary_code" title="Binary code">binary code</a> with the length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">; <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y}</annotation>

</semantics>

</math><img src="./5ea0abffd33a692ded22accc104515a032851dff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.519ex; height:2.009ex;" alt="{\displaystyle x,y}" loading="lazy"> shall be elements of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./56ccd56eb42aa20cbbb79c374fed1b7138e0ebad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.639ex; height:2.843ex;" alt="{\displaystyle \mathbb {F} _{2}^{n}}" loading="lazy">; and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(x,y)}</annotation>

</semantics>

</math><img src="./3772957879a8bbf7946bddf5743c508a1d5072c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.544ex; height:2.843ex;" alt="{\displaystyle d(x,y)}" loading="lazy"> is the distance between those elements.

<div class="mw-heading mw-heading2"><h2 id="Ideal_observer_decoding">Ideal observer decoding</h2></div>

One may be given the message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./041e088c82152e3c4e15e02627f0819bdc909547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.809ex; height:2.843ex;" alt="{\displaystyle x\in \mathbb {F} _{2}^{n}}" loading="lazy">, then ideal observer decoding generates the codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in C}</annotation>

</semantics>

</math><img src="./90e05647e94b6ca619d1f1764db3f12a95a533a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.762ex; height:2.509ex;" alt="{\displaystyle y\in C}" loading="lazy">. The process results in this solution:

</mrow>

</mstyle>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}</annotation>

</semantics>

</math><img src="./78ea098af81d1937daec3bfd770ed7ec10347092.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.167ex; height:2.843ex;" alt="{\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}" loading="lazy"></dd></dl>

For example, a person can choose the codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> that is most likely to be received as the message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> after transmission.

<div class="mw-heading mw-heading3"><h3 id="Decoding_conventions">Decoding conventions</h3></div>

Each codeword does not have an expected possibility: there may be more than one codeword with an equal likelihood of mutating into the received message. In such a case, the sender and receiver(s) must agree ahead of time on a decoding convention. Popular conventions include:

<dl><dd><ol><li>Request that the codeword be resent – <a href="Automatic_repeat-request" class="mw-redirect" title="Automatic repeat-request">automatic repeat-request</a>.</li>

<li>Choose any random codeword from the set of most likely codewords which is nearer to that.</li>

<li>If <a href="Concatenated_error_correction_code" title="Concatenated error correction code">another code follows</a>, mark the ambiguous bits of the codeword as erasures and hope that the outer code disambiguates them</li>

<li>Report a decoding failure to the system</li></ol></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Maximum_likelihood_decoding">Maximum likelihood decoding</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Maximum_likelihood" class="mw-redirect" title="Maximum likelihood">Maximum likelihood</a></div>

Given a received vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./041e088c82152e3c4e15e02627f0819bdc909547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.809ex; height:2.843ex;" alt="{\displaystyle x\in \mathbb {F} _{2}^{n}}" loading="lazy"> <a href="Maximum_likelihood" class="mw-redirect" title="Maximum likelihood">maximum likelihood</a> decoding picks a codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in C}</annotation>

</semantics>

</math><img src="./90e05647e94b6ca619d1f1764db3f12a95a533a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.762ex; height:2.509ex;" alt="{\displaystyle y\in C}" loading="lazy"> that <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">maximizes</a>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}</annotation>

</semantics>

</math><img src="./b854bb9ac05d98b86fc5c5787f97f46439893bbe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.167ex; height:2.843ex;" alt="{\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}" loading="lazy">,</dd></dl>

that is, the codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> that maximizes the probability that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> was received, <a href="Conditional_probability" title="Conditional probability">given that</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> was sent. If all codewords are equally likely to be sent then this scheme is equivalent to ideal observer decoding.

In fact, by <a href="Bayes'_theorem" title="Bayes' theorem">Bayes' theorem</a>,

<mtr>

<mtd>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

<mtd>

</mrow>

<mfrac>

<mrow>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mstyle>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

<mfrac>

<mrow>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}}</annotation>

</semantics>

</math><img src="./c44a6f8e425958af3c8f3d02b7aa9b58e5540c75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.005ex; width:62.694ex; height:13.176ex;" alt="{\displaystyle {\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}}" loading="lazy"></dd></dl>

Upon fixing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {P} (x{\mbox{ received}})}">

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} (x{\mbox{ received}})}</annotation>

</semantics>

</math><img src="./52cb7f093db01168efd475a0234baeb83664382b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.348ex; height:2.843ex;" alt="{\displaystyle \mathbb {P} (x{\mbox{ received}})}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is restructured and

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} (y{\mbox{ sent}})}</annotation>

</semantics>

</math><img src="./c3429f6530f079ae0eef83c07442f905ea884a90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.112ex; height:2.843ex;" alt="{\displaystyle \mathbb {P} (y{\mbox{ sent}})}" loading="lazy"> is constant as all codewords are equally likely to be sent.

Therefore,

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}</annotation>

</semantics>

</math><img src="./b854bb9ac05d98b86fc5c5787f97f46439893bbe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.167ex; height:2.843ex;" alt="{\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}" loading="lazy">

is maximised as a function of the variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> precisely when

</mrow>

</mstyle>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}</annotation>

</semantics>

</math><img src="./78ea098af81d1937daec3bfd770ed7ec10347092.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.167ex; height:2.843ex;" alt="{\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}" loading="lazy">

is maximised, and the claim follows.

As with ideal observer decoding, a convention must be agreed to for non-unique decoding.

The maximum likelihood decoding problem can also be modeled as an <a href="Integer_programming" title="Integer programming">integer programming</a> problem.<a href="#cite_note-Feldman_2005-1">[1]</a>

The maximum likelihood decoding algorithm is an instance of the "marginalize a product function" problem which is solved by applying the <a href="Generalized_distributive_law" title="Generalized distributive law">generalized distributive law</a>.<a href="#cite_note-Aji-McEliece_2000-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Minimum_distance_decoding">Minimum distance decoding</h2></div>

Given a received codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./041e088c82152e3c4e15e02627f0819bdc909547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.809ex; height:2.843ex;" alt="{\displaystyle x\in \mathbb {F} _{2}^{n}}" loading="lazy">, minimum distance decoding picks a codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in C}</annotation>

</semantics>

</math><img src="./90e05647e94b6ca619d1f1764db3f12a95a533a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.762ex; height:2.509ex;" alt="{\displaystyle y\in C}" loading="lazy"> to minimise the <a href="Hamming_distance" title="Hamming distance">Hamming distance</a>:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(x,y)=\#\{i:x_{i}\not =y_{i}\}}</annotation>

</semantics>

</math><img src="./f0d0717b8f2c6bb159f55de8459000a27ac1e45e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.81ex; height:2.843ex;" alt="{\displaystyle d(x,y)=\#\{i:x_{i}\not =y_{i}\}}" loading="lazy"></dd></dl>

i.e. choose the codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> that is as close as possible to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">.

Note that if the probability of error on a discrete memoryless channel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> is strictly less than one half, then minimum distance decoding is equivalent to maximum likelihood decoding, since if

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(x,y)=d,\,}</annotation>

</semantics>

</math><img src="./6ec53064ee65446ba45029a07a51514c0d54e6cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.893ex; height:2.843ex;" alt="{\displaystyle d(x,y)=d,\,}" loading="lazy"></dd></dl>

then:

<mtr>

<mtd>

</mrow>

<mtext> received</mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

<msup>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./f0bd990613c72e656472e5f855b3300279cca1e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.338ex; width:45.418ex; height:9.843ex;" alt="{\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}" loading="lazy"></dd></dl>

which (since p is less than one half) is maximised by minimising d.

Minimum distance decoding is also known as nearest neighbour decoding. It can be assisted or automated by using a <a href="Standard_array" title="Standard array">standard array</a>. Minimum distance decoding is a reasonable decoding method when the following conditions are met:

<dl><dd><ol><li>The probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> that an error occurs is independent of the position of the symbol.</li>

<li>Errors are independent events – an error at one position in the message does not affect other positions.</li></ol></dd></dl>

These assumptions may be reasonable for transmissions over a <a href="Binary_symmetric_channel" title="Binary symmetric channel">binary symmetric channel</a>. They may be unreasonable for other media, such as a DVD, where a single scratch on the disk can cause an error in many neighbouring symbols or codewords.

As with other decoding methods, a convention must be agreed to for non-unique decoding.

<div class="mw-heading mw-heading2"><h2 id="Syndrome_decoding">Syndrome decoding</h2></div>

Syndrome decoding is a highly efficient method of decoding a <a href="Linear_code" title="Linear code">linear code</a> over a noisy channel, i.e. one on which errors are made. In essence, syndrome decoding is minimum distance decoding using a reduced lookup table. This is allowed by the linearity of the code.<a href="#cite_note-Beutelspacher-Rosenbaum_1998-3">[3]</a>

Suppose that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\subset \mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subset \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./f2747dab950a24e090084ba23a584c5db2fe077f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.504ex; height:2.843ex;" alt="{\displaystyle C\subset \mathbb {F} _{2}^{n}}" loading="lazy"> is a linear code of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> with <a href="Parity-check_matrix" title="Parity-check matrix">parity-check matrix</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">. Then clearly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is capable of correcting up to

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }</annotation>

</semantics>

</math><img src="./715615f7baa26e6b19635a0f9865ef76fbe99b0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:12.703ex; height:6.176ex;" alt="{\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }" loading="lazy"></dd></dl>

errors made by the channel (since if no more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> errors are made then minimum distance decoding will still correctly decode the incorrectly transmitted codeword).

Now suppose that a codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./041e088c82152e3c4e15e02627f0819bdc909547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.809ex; height:2.843ex;" alt="{\displaystyle x\in \mathbb {F} _{2}^{n}}" loading="lazy"> is sent over the channel and the error pattern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in \mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in \mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./b269c74424465dfc91df4b09107c61fa431556e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.563ex; height:2.843ex;" alt="{\displaystyle e\in \mathbb {F} _{2}^{n}}" loading="lazy"> occurs. Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z=x+e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z=x+e}</annotation>

</semantics>

</math><img src="./07f8665be684eeeaf05631f200dd12b8d8ea988b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.44ex; height:2.176ex;" alt="{\displaystyle z=x+e}" loading="lazy"> is received. Ordinary minimum distance decoding would lookup the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math><img src="./bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"> in a table of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |C|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |C|}</annotation>

</semantics>

</math><img src="./d9f9114ede7c5dd63e8b1cbd051e11d343b233f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.06ex; height:2.843ex;" alt="{\displaystyle |C|}" loading="lazy"> for the nearest match - i.e. an element (not necessarily unique) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in C}</annotation>

</semantics>

</math><img src="./447d3982c94c23d6b6d01c90da81a6125aa26567.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.614ex; height:2.176ex;" alt="{\displaystyle c\in C}" loading="lazy"> with

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(c,z)\leq d(y,z)}</annotation>

</semantics>

</math><img src="./9301278ec7b40335d09f96c3bcc60b12ba2419bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.555ex; height:2.843ex;" alt="{\displaystyle d(c,z)\leq d(y,z)}" loading="lazy"></dd></dl>

for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in C}</annotation>

</semantics>

</math><img src="./90e05647e94b6ca619d1f1764db3f12a95a533a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.762ex; height:2.509ex;" alt="{\displaystyle y\in C}" loading="lazy">. Syndrome decoding takes advantage of the property of the parity matrix that:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Hx=0}</annotation>

</semantics>

</math><img src="./98b335b9b19a4f5aa4bc4fc37738b05bed7ec557.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.654ex; height:2.176ex;" alt="{\displaystyle Hx=0}" loading="lazy"></dd></dl>

for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in C}</annotation>

</semantics>

</math><img src="./f7fc788379bff7289bdf694ffd68ee690e999eb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.937ex; height:2.176ex;" alt="{\displaystyle x\in C}" loading="lazy">. The syndrome of the received <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z=x+e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z=x+e}</annotation>

</semantics>

</math><img src="./07f8665be684eeeaf05631f200dd12b8d8ea988b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.44ex; height:2.176ex;" alt="{\displaystyle z=x+e}" loading="lazy"> is defined to be:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Hz=H(x+e)=Hx+He=0+He=He}</annotation>

</semantics>

</math><img src="./da507ba61af2357b4f8010345454268c7269aa37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:44.35ex; height:2.843ex;" alt="{\displaystyle Hz=H(x+e)=Hx+He=0+He=He}" loading="lazy"></dd></dl>

To perform <a href="#Maximum_likelihood_decoding">ML decoding</a> in a <a href="Binary_symmetric_channel" title="Binary symmetric channel">binary symmetric channel</a>, one has to look-up a precomputed table of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n-k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n-k}}</annotation>

</semantics>

</math><img src="./ac056f26711f5e3b771cda221a0d99977f7bc4ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.516ex; height:2.676ex;" alt="{\displaystyle 2^{n-k}}" loading="lazy">, mapping <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle He}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle He}</annotation>

</semantics>

</math><img src="./e454641fe1ce40c8ac06756a06cd8b7f35ba4f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.147ex; height:2.176ex;" alt="{\displaystyle He}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">.

Note that this is already of significantly less complexity than that of a <a href="Standard_array" title="Standard array">standard array decoding</a>.

However, under the assumption that no more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> errors were made during transmission, the receiver can look up the value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle He}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle He}</annotation>

</semantics>

</math><img src="./e454641fe1ce40c8ac06756a06cd8b7f35ba4f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.147ex; height:2.176ex;" alt="{\displaystyle He}" loading="lazy"> in a further reduced table of size

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}}</annotation>

</semantics>

</math><img src="./11d58d415f8a1d60cab33677149edb1c9664930c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.9ex; margin-bottom: -0.272ex; width:9.609ex; height:3.509ex;" alt="{\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="List_decoding">List decoding</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="List_decoding" title="List decoding">List decoding</a></div>

<div class="mw-heading mw-heading2"><h2 id="Information_set_decoding">Information set decoding</h2></div>

This is a family of <a href="Las_Vegas_algorithm" title="Las Vegas algorithm">Las Vegas</a>-probabilistic methods all based on the observation that it is easier to guess enough error-free positions, than it is to guess all the error-positions.

The simplest form is due to Prange: Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> be the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\times n}</annotation>

</semantics>

</math><img src="./8e173885ca0f29dd406df781144cd635276c68e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.446ex; height:2.176ex;" alt="{\displaystyle k\times n}" loading="lazy"> generator matrix of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> used for encoding. Select <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> columns of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> at random, and denote by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy"> the corresponding submatrix of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">. With reasonable probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy"> will have full rank, which means that if we let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c'}</annotation>

</semantics>

</math><img src="./f295e32663780aa8800e3106dba9d6e04e57cdc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.692ex; height:2.509ex;" alt="{\displaystyle c'}" loading="lazy"> be the sub-vector for the corresponding positions of any codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=mG}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=mG}</annotation>

</semantics>

</math><img src="./7411b3d7623d4b3ee7d0b0c0660c714fe4ac38de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.972ex; height:2.176ex;" alt="{\displaystyle c=mG}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> for a message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, we can recover <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=c'G'^{-1}}">

<msup>

</msup>

<msup>

<mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=c'G'^{-1}}</annotation>

</semantics>

</math><img src="./e156bdf41cba92753b25c94aa71bfc8b5bcfb515.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.442ex; height:2.676ex;" alt="{\displaystyle m=c'G'^{-1}}" loading="lazy">. Hence, if we were lucky that these <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> positions of the received word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> contained no errors, and hence equalled the positions of the sent codeword, then we may decode.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> errors occurred, the probability of such a fortunate selection of columns is given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)}">

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)}</annotation>

</semantics>

</math><img src="./599b0b274aec2a672608ce7c8738274aba5f4705.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.143ex; height:3.343ex;" alt="{\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)}" loading="lazy">.

This method has been improved in various ways, e.g. by Stern<a href="#cite_note-Stern_1989-4">[4]</a> and <a href="Anne_Canteaut" title="Anne Canteaut">Canteaut</a> and Sendrier.<a href="#cite_note-Ohta_1998-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Partial_response_maximum_likelihood">Partial response maximum likelihood</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="PRML" class="mw-redirect" title="PRML">PRML</a></div>

Partial response maximum likelihood (<a href="PRML" class="mw-redirect" title="PRML">PRML</a>) is a method for converting the weak analog signal from the head of a magnetic disk or tape drive into a digital signal.

<div class="mw-heading mw-heading2"><h2 id="Viterbi_decoder">Viterbi decoder</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Viterbi_decoder" title="Viterbi decoder">Viterbi decoder</a></div>

A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using <a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">forward error correction</a> based on a convolutional code.

The <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> is used as a metric for hard decision Viterbi decoders. The squared <a href="Euclidean_distance" title="Euclidean distance">Euclidean distance</a> is used as a metric for soft decision decoders.

<div class="mw-heading mw-heading2"><h2 id="Optimal_decision_decoding_algorithm_(ODDA)">Optimal decision decoding algorithm (ODDA)</h2></div>

Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system.<a href="#cite_note-6">[6]</a>

<ul><li><a href="Don't_care_alarm" class="mw-redirect" title="Don't care alarm">Don't care alarm</a></li>

<li><a href="Error_detection_and_correction" title="Error detection and correction">Error detection and correction</a></li>

<li><a href="Forbidden_input" class="mw-redirect" title="Forbidden input">Forbidden input</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFFeldmanWainwrightKarger2005" class="citation journal cs1">Feldman, Jon; Wainwright, Martin J.; Karger, David R. (March 2005). "Using Linear Programming to Decode Binary Linear Codes". <a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a>. 51 (3): 954–972. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.6585">10.1.1.111.6585</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2004.842696">10.1109/TIT.2004.842696</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3120399">3120399</a>.</cite>

</li>

<li id="cite_note-Aji-McEliece_2000-2"><a href="#cite_ref-Aji-McEliece_2000_2-0">^</a> <cite id="CITEREFAjiMcEliece2000" class="citation journal cs1">Aji, Srinivas M.; McEliece, Robert J. (March 2000). <a rel="nofollow" class="external text" href="https://authors.library.caltech.edu/1541/1/AJIieeetit00.pdf">"The Generalized Distributive Law"</a> (PDF). <a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a>. 46 (2): 325–343. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F18.825794">10.1109/18.825794</a>.</cite>

</li>

<li id="cite_note-Beutelspacher-Rosenbaum_1998-3"><a href="#cite_ref-Beutelspacher-Rosenbaum_1998_3-0">^</a> <cite id="CITEREFBeutelspacherRosenbaum1998" class="citation book cs1"><a href="Albrecht_Beutelspacher" title="Albrecht Beutelspacher">Beutelspacher, Albrecht</a>; Rosenbaum, Ute (1998). Projective Geometry. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. p. 190. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-48277-1</bdi>.</cite>

</li>

<li id="cite_note-Stern_1989-4"><a href="#cite_ref-Stern_1989_4-0">^</a> <cite id="CITEREFStern1989" class="citation book cs1">Stern, Jacques (1989). "A method for finding codewords of small weight". Coding Theory and Applications. Lecture Notes in Computer Science. Vol. 388. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. pp. 106–113. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0019850">10.1007/BFb0019850</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-51643-9</bdi>.</cite>

</li>

<li id="cite_note-Ohta_1998-5"><a href="#cite_ref-Ohta_1998_5-0">^</a> <cite id="CITEREFOhtaPei1998" class="citation book cs1">Ohta, Kazuo; Pei, Dingyi, eds. (1998). Advances in Cryptology — ASIACRYPT'98. Lecture Notes in Computer Science. Vol. 1514. pp. 187–199. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-49649-1">10.1007/3-540-49649-1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-65109-3</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:37257901">37257901</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFSiamack_Ghadimi2020" class="citation cs2">Siamack Ghadimi (2020), Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system;, Universal Journal of Electrical and Electronic Engineering</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFHill1986" class="citation book cs1">Hill, Raymond (1986). <a rel="nofollow" class="external text" href="https://archive.org/details/firstcourseincod0000hill">A first course in coding theory</a>. Oxford Applied Mathematics and Computing Science Series. <a href="Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-19-853803-5</bdi>.</cite></li>

<li><cite id="CITEREFPless1982" class="citation book cs1"><a href="Vera_Pless" title="Vera Pless">Pless, Vera</a> (1982). <a href="Introduction_to_the_Theory_of_Error-Correcting_Codes" title="Introduction to the Theory of Error-Correcting Codes">Introduction to the theory of error-correcting codes</a>. Wiley-Interscience Series in Discrete Mathematics. <a href="John_Wiley_%26_Sons" class="mw-redirect" title="John Wiley & Sons">John Wiley & Sons</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-08684-0</bdi>.</cite></li>

<li><cite id="CITEREFvan_Lint1992" class="citation book cs1">van Lint, Jacobus H. (1992). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint">Introduction to Coding Theory</a>. <a href="Graduate_Texts_in_Mathematics" title="Graduate Texts in Mathematics">Graduate Texts in Mathematics</a> (GTM). Vol. 86 (2 ed.). <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-54894-2</bdi>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-07" href="https://en.wikipedia.org/wiki/?title=Decoding_methods&oldid=1299335742">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>